今天介紹剩下常見的演算法~
動態規劃法主要是如果一個問提答案與子問題相關的話,就能將大問題拆解成各個小問題,其中與分治法不同的地方是可以讓每一個子問題的答案被儲存起來,以供下次求解時直接取用。
這樣的做法不但能減少再次需要計算的時間,並將這些解組合成大問題的答案,故使用動態規劃將可以解決重複計算的缺點。
這邊用動態規劃法來改寫費柏那序列,已計算過資料不必計算,也不會再往下遞迴,會達到增進效能的目的。
例如想取得第四個費柏那Fib(4),他的遞迴可以利用動態規劃法。
這邊得知遞迴呼叫9次,而執行加法運算4次,Fib(1)重複執行3次,浪費了效能。
fn factorial_dynamic(n: i32) -> i32 {
if n <= 1 {
return n;
}
let mut fib = vec![0; (n + 1) as usize];
fib[1] = 1;
for i in 2..=n{
fib[i as usize] = fib[(i - 1) as usize] + fib[(i - 2) as usize];
}
fib[n as usize]
}
fn main() {
for i in 0..5{
println!("fib({i}) = {}", factorial_dynamic(i));
}
}
疊代法是無法使用公式一次求解,而需反覆運算,例如用迴圈去循環重複程式碼的某些部分來得到答案。
fn factorial_iterative(n: u64) -> u64 {
if n == 0 {
1
} else {
n * factorial_iterative(n - 1)
}
}
fn main() {
let n = 10;
for i in 1..=n{
println!("{i}!= {}", factorial_iterative(i));
}
}
枚舉法又稱窮舉法,是常見的數學方法,也是日常中使用到最多的一種演算法。主要思想就是:枚舉所有可能,根據問題要求來一一枚舉問題的解答,或者為了解決問題分為不重複、不遺漏的情況一一加以解決達到解決整個問題的目的。
優點是可以確保不會錯過任何可能的解決方案,但缺點是在某些情況下可能效率較低,特別是可能情況非常多時。
例如:
我們將A與B字串連接起來,也就是將B字串接到A字串後方,用B字串的每一個字元,從第一個字元開始逐步連結到A字串最後一個字元。
枚舉法的概念就是將要分析的項目在不遺漏的情況下逐一枚舉列出,再從所枚舉列出的項目中去找自己所需要的目標。
以下簡單的範例:
列出1~100之間所有3的倍數的整數,以枚舉法的做法就是從1開始到100逐一列出所有整數,並一邊枚舉一邊檢查該枚舉的數字是否為3的倍數,如果不是就不輸出,如果是就印出來。
fn main() {
for i in 1..=100{
if i % 3 == 0{
println!("{}",i);
}
}
}
回朔法也是枚舉法的一種,對於某些問題回朔法是可以找出所有解的一般性演算法,可以隨時避免枚舉不正確的數值,一但發現不正確的數值,就不遞迴至下一層,而是回朔到上一層來節省時間。
這種走不通就退回再走的方式,主要是在搜尋過程中尋找問題的解,當發現不滿足求解條件時,就回朔返回,嘗試別的路徑,避免無效搜索。
最常就是用在搜尋、遊戲、排列組合等等
這邊找個好理解的排列組合範例來解說:
找出數組中所有可能的子集
fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
let mut current_subset = Vec::new();
fn backtrack(start: usize, current_subset: &mut Vec<i32>, result: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
// 每次遞迴都將當前子集合添加到結果中
result.push(current_subset.clone());
for i in start..nums.len() {
current_subset.push(nums[i]);
// 繼續遞迴搜索,從下一個元素開始
backtrack(i + 1, current_subset, result, nums);
// 結束當前選擇,進行回朔
current_subset.pop();
}
}
backtrack(0, &mut current_subset, &mut result, &nums);
result
}
fn main() {
let nums = vec![1,2,3];
let subsets = subsets(nums.clone());
for subset in subsets {
println!("{:?}", subset);
}
}
出來的結果就會像是
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]
今天把比較常見的演算法介紹完,排除程式方面,其實生活中就有遇過很多相關的,像是回朔法就蠻常見的,外面投注站都有大樂透包牌全餐那種,就是經典的排列組合,這邊可以思考一下除了工作運用外還有哪裡會遇到呢?這樣有助於思考(其實是挺痛苦的因為好抽象)。
目前應該不會太難吧㋡㋡!!
要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 𓁏𓁏𓁏。